package Algorithm.DynamicPlanning;

public class Code16_MoneyWays {

    public static int moneyWays(int[] arbitrary, int[] onlyone, int money){
        if (money < 0){
            return 0;
        }
        if ((arbitrary == null || arbitrary.length == 0)
                && (onlyone == null || onlyone.length == 0)){
            return money == 0 ? 1 : 0;
        }
        // 任意张的数组
        int[][] dparb = getDpArb(arbitrary, money);
        int[][] dpone = getDpOne(onlyone, money);
        int res = 0;
        // 任意张的数组没有，一张的数组有
        if (dparb == null){
            return dpone[dpone.length - 1][money];
        }
        // 任意张的数组有，一张的数组没有
        if (dpone == null){
            return dparb[dparb.length - 1][money];
        }
        // 两个数组都有，遍历两个dp最后一行，排列组合成money
        for (int j = 0; j <= money; j++) {
            res += dparb[dparb.length - 1][j] * dpone[dpone.length - 1][money - j];
        }
        return res;
    }

    public static int[][] getDpArb(int[] arbitrary, int money){
        if (arbitrary == null || arbitrary.length == 0){
            return null;
        }
        int[][] dp = new int[arbitrary.length][money + 1];
        for (int i = 0; i < dp.length; i++){
            dp[i][0] = 1;
        }
        for (int j = 1; j * arbitrary[0] < dp[0].length; j++) {
            dp[0][j * arbitrary[0]] = 1;
        }
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++){
                dp[i][j] = dp[i - 1][j];
                dp[i][j] += (j - arbitrary[i] >= 0) ? dp[i][j - arbitrary[i]] : 0;
            }
        }
        return dp;
    }

    public static int[][] getDpOne(int[] onlyone, int money){
        if (onlyone == null || onlyone.length == 0){
            return null;
        }
        int[][] dp = new int[onlyone.length][money + 1];
        for (int i = 0; i < dp.length; i++){
            dp[i][0] = 1;
        }
        if (onlyone[0] <= money){
            dp[0][onlyone[0]] = 1;
        }
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++){
                // 前i-1就凑到了j;前i-1凑到了j-onlyone[i]
                dp[i][j] = dp[i - 1][j];
                dp[i][j] += (j - onlyone[i] >= 0) ? dp[i - 1][j - onlyone[i]] : 0;
            }
        }
        return dp;
    }

    public static void main(String[] args) {
        int[] arbitrary = {7,3,5};
        int[] onlyone = {5,3,7,5};
        int money = 10;
        System.out.println(moneyWays(arbitrary, onlyone, money));
    }
}
